#include<vector>
using std::vector;


class Solution {
public:
    vector<int> countBits(int n) {
        vector<int> counts(n+1, 0);
        for (int i = 1; i <= n; i++) {
            if (i % 2 == 0) counts[i] = counts[i / 2];
            else counts[i] = counts[i-1] + 1;
        }
        return counts;
    }
};